{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Многопоточность. Продвинутый материал."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Документация:\n",
    "* https://en.cppreference.com/w/cpp/atomic\n",
    "* https://en.cppreference.com/w/cpp/atomic/memory_order\n",
    "\n",
    "Серия статей от Jeff Pershing на понимание atomics, memory model && lock free:\n",
    "* https://preshing.com/20120515/memory-reordering-caught-in-the-act/\n",
    "* https://preshing.com/20120612/an-introduction-to-lock-free-programming\n",
    "* https://preshing.com/20120625/memory-ordering-at-compile-time/\n",
    "* https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/\n",
    "* https://preshing.com/20120913/acquire-and-release-semantics/\n",
    "* https://preshing.com/20120930/weak-vs-strong-memory-models/\n",
    "* https://preshing.com/20121019/this-is-why-they-call-it-a-weakly-ordered-cpu/\n",
    "* https://preshing.com/20130618/atomic-vs-non-atomic-operations/\n",
    "* https://preshing.com/20130702/the-happens-before-relation/\n",
    "* https://preshing.com/20130922/acquire-and-release-fences/\n",
    "* https://preshing.com/20130823/the-synchronizes-with-relation/\n",
    "* https://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/\n",
    "* https://preshing.com/20131125/acquire-and-release-fences-dont-work-the-way-youd-expect/\n",
    "* https://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/\n",
    "* В конце своих статей Джефф даёт ссылки на полезные материалы, их тоже рекомендуется почитать. Не стоит рассчитывать, что управитесь со всем багажом знаний за полчасика.\n",
    "* И в комментарии к статьям приходят специалисты (Herb Sutter, Tarvis Downs), и объясняют, в чём Джефф был не прав, поэтому комментарии желательно тоже смотреть.\n",
    "\n",
    "Другие статьи:\n",
    "* [Memory Barriers: a Hardware View for Software Hackers](http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf)\n",
    "* [LINUX KERNEL MEMORY BARRIERS](https://www.kernel.org/doc/Documentation/memory-barriers.txt)\n",
    "* [Максим Хижинский. Lock-free Data Structures. Basics: Atomicity and Atomic Primitives](https://kukuruku.co/post/lock-free-data-structures-basics-atomicity-and-atomic-primitives/)\n",
    "* [Bjarne Stroustrup про ABA-проблему и как её решать](http://www.stroustrup.com/isorc2010.pdf)\n",
    "\n",
    "Доклады про многопоточность:\n",
    "* [CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced. What do they really do?”](https://www.youtube.com/watch?v=ZQFzMfHIxng)\n",
    "* [CppCon 2018: Bryce Adelstein Lelbach “The C++ Execution Model”](https://www.youtube.com/watch?v=FJIn1YhPJJc)\n",
    "* [CppCon 2019: Bryce Adelstein Lelbach “The C++20 Synchronization Library”](https://www.youtube.com/watch?v=Zcqwb3CWqs4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### thread-based vs task-based модели организации вычислений"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В первой лекции про многопоточность мы неявно затронули это разделение.\n",
    "\n",
    "Повторим материал, вспомним задачу параллельного поиска максимума в массиве."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для простоты демонстрации вынесем функцию, которая считает максимум на части массива:\n",
    "    \n",
    "```c++\n",
    "int max_by_block(const std::vector<int>& arr, const unsigned block_ix, const unsigned blocks_count)\n",
    "{\n",
    "    const unsigned block_size = arr.size() / blocks_count;\n",
    "    \n",
    "    // для простоты демонстрации, чтобы не обрабатывать хвосты и ошибки\n",
    "    assert(block_size);\n",
    "    assert(block_size * blocks_count == arr.size());\n",
    "    assert(block_ix < blocks_count);\n",
    "\n",
    "    const unsigned start_ix = block_size * block_ix;\n",
    "    return *max_element(begin(arr) + start_ix,\n",
    "                        begin(arr) + start_ix + block_size);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решение через потоки:\n",
    "\n",
    "```c++\n",
    "int parallel_max(const std::vector<int>& arr, const unsigned threads_count)\n",
    "{\n",
    "    // maximum per threads\n",
    "    std::vector<int> results(threads_count, 0);\n",
    "\n",
    "    // create threads to search for maximum\n",
    "    std::vector<std::thread> threads;\n",
    "    for (unsigned i = 0; i < threads_count; ++i)\n",
    "        threads.emplace_back([i, threads_count, &results](){\n",
    "            results[i] = max_by_block(arr, i, threads_count);\n",
    "        });\n",
    "\n",
    "    // wait for threads to complete\n",
    "    for (auto& t : threads)\n",
    "        t.join();\n",
    "\n",
    "    return *max_element(begin(results), end(results));\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решение через async:\n",
    "\n",
    "```c++\n",
    "int parallel_max(const std::vector<int>& arr, const unsigned tasks_count)\n",
    "{\n",
    "    // создать |tasks_count| фоновых задач\n",
    "    std::vector<std::future<int>> futures;\n",
    "    for (unsigned i = 0; i < tasks_count; ++i)\n",
    "        futures.emplace_back(std::async(std::launch::async,\n",
    "                                        [&arr, =]() { return max_by_block(arr, i, tasks_count); }));\n",
    "\n",
    "    // collect results and reduce\n",
    "    int res = INT_MIN;\n",
    "    for (auto& f: futures)\n",
    "        res = std::max(res, f.get());\n",
    "\n",
    "    return res;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вы можете отметить, что визуально разница не так уж и велика, но нужно отметить следующее:\n",
    "    \n",
    "* в решении через потоки:\n",
    "    * строго зафиксировано число потоков, на котором запускаются вычисления\n",
    "    * строго задан момент создания потоков и момент их уничтожения\n",
    "    * пользователь выражает свои намерения в терминах _\"создать поток, запустить вычисления, уничтожить поток\"_\n",
    "    \n",
    "\n",
    "* в решении через `async` (через задачи) от пользователя скрывается информация \n",
    "    * от пользователя через интерфейс async спрятана (почти) информация сколько создаётся потоков, когда они создаются, продолжают ли они жить после выполнения задачи\n",
    "    * пользователь выражает свои намерения в терминах _\"выполнить фоновую задачу\"_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### executors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Развитие task-based моделей организации служат Executors - классы / мезанизмы управления фоновыми задачами.\n",
    "\n",
    "Пока что в С++ executors не стандартизированы, только в процессе, поэтому каждый пишет во что горазд. В целом executor может позволять делать следующее:\n",
    "* запуск фоновой задачи\n",
    "* отмена фоновой задачи\n",
    "* поддержка приоритетов задач\n",
    "* поддержка зависимостей между задачами\n",
    "* управление внутренним пулом потоков:\n",
    "    * фиксированное число потоков / плавающее число потоков\n",
    "    * момент создания и уничтожения потоков\n",
    "* управление внутренней очередью задач"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ориентировочный вариант интерфейса executor (понятно, тут у каждого свои вариации):\n",
    "    \n",
    "```c++\n",
    "class Executor\n",
    "{\n",
    "public:\n",
    "    // кол-во потоков для выполнения задач задаём в конструкторе,\n",
    "    // пусть он сам принимает решение, когда система перегружена,\n",
    "    // и требуется отсыпать ещё потоков, либо наоборот, задачи\n",
    "    // кончились и потоки можно уничтожить, высвободить память\n",
    "    Executor(const unsigned min_threads_count,\n",
    "             const unsigned max_threads_count);\n",
    "    \n",
    "    // запланировать выполнение задачи\n",
    "    // (вариант, принятый +- в chromium)\n",
    "    //\n",
    "    // Callable - может быть std::function или\n",
    "    // std::packaged_task или любой другой класс,\n",
    "    // умеющий представлять собой некоторую задачу\n",
    "    //\n",
    "    // TaskParams - набор параметров задачи, могут,\n",
    "    // например, содержать приоритет, отладочную\n",
    "    // инфомрацию и другие параметры, отвечающие на\n",
    "    // вопрос \"как выполнить эту задачу\"\n",
    "    //\n",
    "    // Callback - куда отсылать результат задачи\n",
    "    template<typename Callable, typename Callback>\n",
    "    bool post_task(Callable&& task, TaskParams params, Callback&& callback);\n",
    "    \n",
    "    // вариант реализации через std::future\n",
    "    // (+- более в стиле std::async)\n",
    "    template<typename Result, typename Callable>\n",
    "    std::future<Result> post_task(Callable&& task, TaskParams params);\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно, как вариант, создать экземпляр класса `Executor` как глобальную переменную. И надо аккуратно проработать потокобезопасность такого решения (либо однопоточный доступ до объекта либо потокобезопасная реализация)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Когда пользоваться подходом через потоки, когда - через задачи - зависит от... задачи.\n",
    "\n",
    "\n",
    "**Пример**, когда решение через потоки может быть лучше:\n",
    "\n",
    "Параллельный поиск оптимума в горячем месте программы\n",
    "  * нужно строго контроллировать количество потоков\n",
    "  * нужно строго контроллировать время их жизни\n",
    "  * нужна синхронизация меджу потоками\n",
    "\n",
    "\n",
    "**Пример**, когда решение через задачи может быть лучше:\n",
    "\n",
    "Мы пишем браузер.\n",
    "\n",
    "* <i>задача 1</i>: пользователь открыл сайт, нужно распарсить ответ от сервера, затем распарсить html-ку и отдать её на рендеринг.\n",
    "\n",
    "  Нельзя парсить в главном потоке программы, иначе UI подвиснет и не будут реагировать кнопки меню. Нужно парсить в фоне.\n",
    "  \n",
    "  Скорость выполнения этой задачи важна для пользователя, её влияние на UX приложения критично.\n",
    "  \n",
    "  <i>Решение</i>: запостить фоновую задачу парсинга ответа и html-ки с высоким приоритетом.\n",
    "  \n",
    "  <i>Псевдокод:</i>\n",
    "  \n",
    "```c++\n",
    "void process_server_response(const Response& response)\n",
    "{\n",
    "    global_executor.post_task(bind(parse_server_response, response),\n",
    "                              TaskParams{ HIGH_PRIORITY },\n",
    "                              process_raw_html);\n",
    "}\n",
    "\n",
    "void process_raw_html(const std::string& html)\n",
    "{\n",
    "    global_executor.post_task(bind(parse_html, html),\n",
    "                              TaskParams{ HIGH_PROPRITY },\n",
    "                              render_html);\n",
    "}\n",
    "\n",
    "void render_html(const HTML& html)\n",
    "{\n",
    "    // rendering code ...\n",
    "}\n",
    "```\n",
    "\n",
    "\n",
    "* <i>задача 2</i>: пользователь запускает установку расширения в браузере.\n",
    "\n",
    "  Установка сторонних расширений - процесс длительный. Не критично, если расширение не установится моментально, но и час установку ждать никто не будет.\n",
    "\n",
    "  <i>Решение</i>: запостить фоновую задачу по установке расширения со средним приоритетом.\n",
    "  \n",
    "  \n",
    "* <i>задача 3</i>: Браузер периодически запускает очистку данных на диске (протухшие кеши страниц / изображений, удалённые оставшиеся на диске расширения, прочистка БД от мусора)\n",
    "\n",
    "  Цель - освободить место на диске, которое занято мусором, и слегка ускорить работу, уменьшив объём данных.\n",
    "  \n",
    "  Пользователю всё равно сколько будет идти задача, он даже не знает о её существовании.\n",
    "  \n",
    "  <i>Решение</i>: запостить фоновую задачу очистки с самым низким приоритетом. Если потоки executor-а будут забиты высокоприоритетными задачами, и наша не стартует, никто не заметит проблемы, очистка отработает на следующий запуск браузера или через час/день/месяц."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: Task-based орагнизация - более высокий уровень абстракции чем thread-based. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: В домашнем задании про тайловую карту С++ вам нужно будет сделать именно task-based решение с фиксированным числом фоновых потоков."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### atomic basics (since C++11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вспомним задачу параллельного суммирования массива из второй лекции на многопоточность.\n",
    "\n",
    "Её реализация с ошибкой:\n",
    "\n",
    "```c++\n",
    "int parallel_sum(const std::vector<int>& v, const unsigned threads_count)\n",
    "{\n",
    "    const unsigned len = v.size() / threads_count;\n",
    "    assert(len * threads_count == v.size());\n",
    "\n",
    "    int rv = 0;\n",
    "\n",
    "    std::vector<std::thread> threads;\n",
    "    for (unsigned i = 0; i < threads_count; ++i)\n",
    "        threads.emplace_back([&v, &rv, i, len](){\n",
    "            for (unsigned ix = len * i, final_ix = len * (i + 1); ix < final_ix; ++ix)\n",
    "                 rv += v[ix];\n",
    "        });\n",
    "\n",
    "    for (auto& t: threads)\n",
    "        t.join();\n",
    "\n",
    "    return rv;\n",
    "}\n",
    "```\n",
    "\n",
    "**Вопрос**: напомните, в чём ошибка?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во второй лекции проблему решали через `mutex`.\n",
    "\n",
    "**Вопрос**: как лучше всего решить задачу, чтобы синхронизаций было поменьше?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сейчас будем писать тоже неидеальное решение - через `std::atomic`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Атомарность операции означает, что никакой из потоков не может отследить промежуточное состояние операции: либо состояние до изменений, либо состояние после изменений.\n",
    "\n",
    "**Пример:**\n",
    "\n",
    "`std::atomic<int>` имеет операцию `fetch_add`:\n",
    "\n",
    "`var.fetch_add(int x)` имеет три условных стадии выполнения:\n",
    "\n",
    "1. считать текущее значение из памяти в регистр\n",
    "2. увеличить регистр на значение `x`\n",
    "3. записать значение регистра в память\n",
    "\n",
    "Никакой поток не может вклиниться в работу с `var`, пока выполняются шаги 1-2-3. Он либо работает с `var` до шага 1, либо после шага 3.\n",
    "\n",
    "\n",
    "**Вопрос:** в примере ниже:\n",
    "1. какое значение `counter` возможно после того как потоки выполняют свою работу?\n",
    "2. если бы гарантии атомарности не было, какое значение мы могнли бы получить?\n",
    "\n",
    "```c++\n",
    "std::atomic<int> counter{0};\n",
    "\n",
    "void thread_1_worker() { counter.fetch_add(1); }\n",
    "void thread_2_worker() { counter.fetch_add(1); }\n",
    "\n",
    "std::thread t1(thread_1_worker), t2(thread_2_worker);\n",
    "t1.join(); t2.join();\n",
    "```\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Из документации по типу `atomic<T>`:\n",
    "\n",
    "> Each instantiation and full specialization of the `std::atomic` template defines an atomic type. If one thread writes to an atomic object while another thread reads from it, the behavior is well-defined (see memory model for details on data races)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Какие типы `T` можно подставлять?\n",
    "\n",
    "Обратимся опять к документации:\n",
    "\n",
    "> The primary `std::atomic` template may be instantiated with any `TriviallyCopyable` type `T` satisfying both `CopyConstructible` and `CopyAssignable`. The program is ill-formed if any of following values is false:\n",
    "* `std::is_trivially_copyable<T>::value`\n",
    "* `std::is_copy_constructible<T>::value`\n",
    "* `std::is_move_constructible<T>::value`\n",
    "* `std::is_copy_assignable<T>::value`\n",
    "* `std::is_move_assignable<T>::value`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Т.е. для любого `TriviallyCopyable` типа `T` объект типа `std::atomic<T>` потокобезопасен на чтение и запись.\n",
    "\n",
    "```c++\n",
    "struct Point\n",
    "{\n",
    "    float x;\n",
    "    float y;\n",
    "    float z;\n",
    "};\n",
    "\n",
    "std::atomic<Point> p;\n",
    "\n",
    "void thread_1_worker() {\n",
    "    p = Point{1.f, 2.f, 3.f};  // ok\n",
    "}\n",
    "\n",
    "void thread_2_worker() {\n",
    "    Point x = p;  // ok\n",
    "}\n",
    "```\n",
    "\n",
    "А вот эти примеры - ill-formed:\n",
    "\n",
    "```c++\n",
    "std::atomic<std::string> s;  // ill-formed\n",
    "std::atomic<std::vector<int>> v;  // ill-formed\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### atomic vs mutex: performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для каких-то сложных типов (например, `Point`) `std::atomic` реализуется через `std::mutex` или аналогичным образом.\n",
    "\n",
    "Если бы так было для всех типов, то особого смысла в `std::atomic` бы не было.\n",
    "\n",
    "Смысл в том, что для простых типов (`int`, `bool`, `int64_t` ...) многие CPU поддерживают более дешёвые способы синхронизации. Набор типов и степень их дешевизны зависят от архитектуры CPU."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем реализацию паралелльной суммы через `std::atomic<int>`:\n",
    "\n",
    "```c++\n",
    "int parallel_sum(const std::vector<int>& v, const unsigned threads_count)\n",
    "{\n",
    "    const unsigned len = v.size() / threads_count;\n",
    "    assert(len * threads_count == v.size());\n",
    "\n",
    "    std::atomic<int> rv{0};\n",
    "\n",
    "    std::vector<std::thread> threads;\n",
    "    for (unsigned i = 0; i < threads_count; ++i)\n",
    "        threads.emplace_back([&v, &rv, i, len](){\n",
    "            for (unsigned ix = len * i, final_ix = len * (i + 1); ix < final_ix; ++ix)\n",
    "                 rv.fetch_add(v[ix]);\n",
    "        });\n",
    "\n",
    "    for (auto& t: threads)\n",
    "        t.join();\n",
    "\n",
    "    return rv;\n",
    "}\n",
    "```\n",
    "\n",
    "И через `std::mutex`:\n",
    "\n",
    "```c++\n",
    "int parallel_sum(const std::vector<int>& v, const unsigned threads_count)\n",
    "{\n",
    "    const unsigned len = v.size() / threads_count;\n",
    "    assert(len * threads_count == v.size());\n",
    "\n",
    "    int rv = 0;\n",
    "    std::mutex m;\n",
    "\n",
    "    std::vector<std::thread> threads;\n",
    "    for (unsigned i = 0; i < threads_count; ++i)\n",
    "        threads.emplace_back([&v, &rv, &m, i, len](){\n",
    "            for (unsigned ix = len * i, final_ix = len * (i + 1); ix < final_ix; ++ix)\n",
    "            {\n",
    "                std::lock_guard guard(m);\n",
    "                rv += v[ix];                \n",
    "            }\n",
    "        });\n",
    "\n",
    "    for (auto& t: threads)\n",
    "        t.join();\n",
    "\n",
    "    return rv;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И сравним производительность на 6 потоках (тестовая машинка: 6 физических ядер Intel Core i5-8400):\n",
    "\n",
    "```sh\n",
    "g++ parallel_sum_atomic.cpp -lpthread -O3 -std=c++17 -o sum_atomic.exe && ./sum_atomic.exe\n",
    "g++ parallel_sum_mutex.cpp  -lpthread -O3 -std=c++17 -o sum_mutex.exe  && ./sum_mutex.exe\n",
    "```\n",
    "\n",
    "вывод:\n",
    "\n",
    "```sh\n",
    "parallel sum atomic:\n",
    "  size          = 60000000\n",
    "  threads_count = 6\n",
    "  result        = 60000000\n",
    "  time, sec     = 1.60537\n",
    " \n",
    "parallel sum mutex:\n",
    "  size          = 60000000\n",
    "  threads_count = 6\n",
    "  result        = 60000000\n",
    "  time, sec     = 6.33526\n",
    "```\n",
    "\n",
    "В зависимости от примитива синхронизации получилось добиться 4-х кратного ускорения алгоритма, что существенно.\n",
    "Такой эффект достигается за счёт того, что в алгоритме слишком агрессивно используется синхронизация данных."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы оценить что происходит в бинарном коде закинем файл на godbolt.org (gcc 9.2 -O3 -std=c++17):\n",
    "\n",
    "```c++\n",
    "#include <atomic>\n",
    "#include <mutex>\n",
    "\n",
    "int mutexed_counter = 0;\n",
    "std::mutex m;\n",
    "\n",
    "std::atomic<int> atomic_counter{0};\n",
    "\n",
    "void add_mutexed(int value)\n",
    "{\n",
    "    std::lock_guard guard{m};\n",
    "    mutexed_counter += value;\n",
    "}\n",
    "\n",
    "void add_atomic(int value)\n",
    "{\n",
    "    atomic_counter += value;\n",
    "}\n",
    "```\n",
    "\n",
    "**Вопрос**: Перед тем как посмотреть на ответ, подскажите, что происходит внутри `lock_guard` и `mutex` в этом коде?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```asm\n",
    "add_mutexed(int):\n",
    "        push    rbp\n",
    "        mov     ebp, OFFSET FLAT:_ZL28__gthrw___pthread_key_createPjPFvPvE\n",
    "        push    rbx\n",
    "        mov     ebx, edi\n",
    "        sub     rsp, 8\n",
    "        test    rbp, rbp\n",
    "        je      .L2\n",
    "        mov     edi, OFFSET FLAT:m\n",
    "        call    __gthrw_pthread_mutex_lock(pthread_mutex_t*)\n",
    "        test    eax, eax\n",
    "        jne     .L12\n",
    ".L2:\n",
    "        add     DWORD PTR mutexed_counter[rip], ebx\n",
    "        test    rbp, rbp\n",
    "        je      .L1\n",
    "        add     rsp, 8\n",
    "        mov     edi, OFFSET FLAT:m\n",
    "        pop     rbx\n",
    "        pop     rbp\n",
    "        jmp     __gthrw_pthread_mutex_unlock(pthread_mutex_t*)\n",
    ".L1:\n",
    "        add     rsp, 8\n",
    "        pop     rbx\n",
    "        pop     rbp\n",
    "        ret\n",
    ".L12:\n",
    "        mov     edi, eax\n",
    "        call    std::__throw_system_error(int)\n",
    "        \n",
    "add_atomic(int):\n",
    "        lock add        DWORD PTR atomic_counter[rip], edi\n",
    "        ret\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Внутри `add_mutexed` можно наблюдать уход в ядро ОС через `pthread`.\n",
    "\n",
    "А весь `add_atomic` - одна инструкция `lock add` - особая атомарная инструкция сложения."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### atomics: hardware"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сначала рассмотрим hardware-нюансы обзорно.\n",
    "\n",
    "Вспомним многоуровневую организацию кешей памяти:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"cpu_caches_ram.png\" width=50% height=50% />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "При работе многопоточного приложения одна и та же ячейка памяти может оказаться одновременно в разных кешах L1 разных CPU.\n",
    "\n",
    "Если при этом происходит только чтение из памяти, то проблем не возникает. Возникают проблемы, когда нужна запись.\n",
    "\n",
    "Записанное значение должно \"просочиться\" по всем уровням иерархии кешей вплоть до RAM... и обновиться в кешах соседних CPU.\n",
    "\n",
    "Процесс \"просачивания\" не быстрый, другие CPU могут читать устаревшее значение или попытаться записать своё.\n",
    "\n",
    "Особые atomic-инструкции решают эту проблему, они гарантируют, что записанное одним CPU значение \"просочится\" по всей иерархии кешей и будет корректно прочитано другими CPU.\n",
    "\n",
    "Поэтому атомарные инструкции (как правило - зависит от железа) медленнее аналогичных неатомарных инструкций:\n",
    "  * `+=` для `std::atomic<int>` будет медленнее чем для `int`\n",
    "  * также работа с `std::atomic<int>` отключает некоторые оптимизации компилятора (подробности в разделе про instruction reordering && memory model)\n",
    "\n",
    "Это упрощённое описание. Пока что его будет достаточно для дальнейшей работы. Большие нюансы о гарантиях и оптимизации atomic - раздел про memory model, о нём позже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### instructions reordering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* https://preshing.com/20120625/memory-ordering-at-compile-time/\n",
    "* https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Переупорядочивание инструкций - изменение порядка выполняемых команд \"без видимых эффектов\" - одна из оптимизаций программ, будучи полностью прозрачной для однопоточного кода, начинает играть роль для некорректного многопоточного кода (для корректного всё хорошо).\n",
    "\n",
    "Важно, что _ассемблерные_ инструкции не могут быть переупорядочены, если между ними есть зависимость по данным."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Переупорядочивание инструкций можно разделить на 2 типа:\n",
    "* в compile time\n",
    "* в runtime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**compile-time**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во-первых, компилятор может решить, что лучше команды выполнять не в той последовательности, в которой их описал программист.\n",
    "\n",
    "Рассмотрим такой код:\n",
    "\n",
    "```c++\n",
    "\n",
    "double some_value = 0.;\n",
    "bool value_is_set = false;\n",
    "\n",
    "\n",
    "void run_setup()\n",
    "{\n",
    "    some_value = 3.14;    // между some_value и value_is_set нет зависимости\n",
    "    value_is_set = true;  // по данным, компилятор вправе поменять присванивания местами\n",
    "}\n",
    "\n",
    "void process()\n",
    "{\n",
    "    if (value_is_set)\n",
    "        assert(some_value == 3.14);\n",
    "}\n",
    "```\n",
    "\n",
    "В однопоточном приложении здесь всё будет хорошо, а в многопоточном и так плохо т.к. нет нужных синхронизаций, но переупорядочивание инструкций может увеличить вероятность ошибки.\n",
    "\n",
    "\n",
    "Другой пример с переупорядочиванием инструкций, когда зависимость по данным есть в плюсовом коде, но её нет на увроне инструкций ассемблера:\n",
    "\n",
    "```c++\n",
    "int A, B;\n",
    "\n",
    "void foo()\n",
    "{\n",
    "    A = B + 1;\n",
    "    B = 0;\n",
    "}\n",
    "```\n",
    "\n",
    "Здесь компилятор так же вправе сгенерировать запись в ячейку памяти B раньше чем в A:\n",
    "\n",
    "либо так:\n",
    "\n",
    "```asm\n",
    "mov     eax, DWORD PTR _B\n",
    "add     eax, 1\n",
    "mov     DWORD PTR _A, eax\n",
    "mov     DWORD PTR _B, 0\n",
    "```\n",
    "\n",
    "либо так:\n",
    "\n",
    "```asm\n",
    "mov     eax, DWORD PTR B\n",
    "mov     DWORD PTR B, 0\n",
    "add     eax, 1\n",
    "mov     DWORD PTR A, eax\n",
    "```\n",
    "\n",
    "Опять же, для однопоточного кода такие трюки должны быть прозрачны. Они начинают играть свою роль только для многопоточного кода.\n",
    "\n",
    "**Замечание**: есть способ запретить копилятору переупорядочивать некоторые операции, добавив барьер, [подробнее - читайте по ссылке выше](https://preshing.com/20120625/memory-ordering-at-compile-time/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**runtime**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во-вторых, даже если компилятор сохранил последовательность команд программиста, CPU может иметь своё мнение, и решить, что быстрее будет их выполнить в ином порядке."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим пример такого устройства:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](cpu_mem_organization.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой схеме у каждого ядра \"своя личная область работы\" - кеш L1, а \"общая область\" - кеш L2 + RAM.\n",
    "\n",
    "Рассмотрим случай, когда в какой-то программе поток 1 выполняет код на ядре 1, а поток 2 выполняет код на ядре 2:\n",
    "\n",
    "```c++\n",
    "int x = 0, y = 0, z = 0;\n",
    "int a = 0, b = 0, c = 0;\n",
    "\n",
    "void thread_1_worker_on_cpu_1() {\n",
    "    x = 1; y = 2; z = 3;\n",
    "    \n",
    "    if (b == 5)\n",
    "        assert(a == 4);  // fail\n",
    "}\n",
    "\n",
    "void thread_2_worker_on_cpu_2() {\n",
    "    a = 4; b = 5; c = 6;\n",
    "\n",
    "    if (y == 2)\n",
    "        assert(x == 1);  // fail\n",
    "}\n",
    "```\n",
    "\n",
    "В таком коде нет гарантий на порядок записи / чтения между \"личной областью работы\" и \"общей областью работы\".\n",
    "\n",
    "* Порядок, кто из `x`, `y`, `z` раньше попадёт в L2 + RAM не определён, так же как и время, через которое они туда попадут.\n",
    "  * вполне может оказаться так, что z улетит в RAM первым, а x и y ещё долго провисят недоставленными по адресу в L1\n",
    "* Аналогично, не определён порядок попадания `a`, `b`, `c` в \"общую область работы\"\n",
    "* Хуже того, не определён порядок попадания `x`, `y`, `z` в \"личную область работы\" потока 2, т.е. при чтении тоже нет гарантий, что поток 2, увидев `y == 2`, получит `x == 1`\n",
    "* Ещё хуже, если запустить поток 3 на cpu 3, он может увидеть совсем другую последовательность значений `x`, `y`, `z`, чем поток 2\n",
    "\n",
    "При таких условиях многопоточных код писать невозможно. Чтобы справляться с этими проблемами есть особые барьеры памяти (их много и разных видов), о них поговорим чуть позже.\n",
    "\n",
    "Если коротко, без использования барьеров памяти:\n",
    "* значения на запись уходят в \"общую область\" сколь угодно долго и в произвольном порядке\n",
    "* значения на чтение приходят в \"личную область\" сколько угодно долго и в произвольном порядке"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### double checked locking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/\n",
    "\n",
    "http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html\n",
    "\n",
    "https://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DCLP - double checked locking pattern - популярный шаблон организации потокобезопасного доступа к данным/объектам с ленивой инициализацией. Пример: синглтоны с ленивой инициализацией."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос-напоминалка**: что такое синглтон?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Однопоточный вариант организации ленивого синглтона:\n",
    "    \n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "    static Singleton* object;\n",
    "\n",
    "public:\n",
    "    static Singleton* instance()\n",
    "    {\n",
    "        if (!object)\n",
    "            object = new Singleton;\n",
    "        return object;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "**Вопрос**: Почему эта реализация не работает в многопоточной среде? Приведите пример последовательности выполнения потоков, при котором возникает ошибка."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Многопоточный вариант реализации ленивого синглтона:\n",
    "    \n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "    static Singleton* object;\n",
    "    static std::mutex mtx;\n",
    "\n",
    "public:\n",
    "    static Singleton* instance()\n",
    "    {\n",
    "        std::lock_guard guard(mtx);\n",
    "        \n",
    "        if (!object)\n",
    "            object = new Singleton;\n",
    "        return object;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "**Вопрос**: корректна ли эта реализация? Какие у неё проблемы?\n",
    "\n",
    "<details>\n",
    "<summary>ответ</summary>\n",
    "<p>\n",
    "\n",
    "Корректна, но очень дорого: когда синглтон инициализирован каждый из потоков спотыкается об `mutex` при доступе к синглтону. `mutex`-ы уходят в kernel space, хочется что-нибудь подешевле.\n",
    "\n",
    "</p>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вариант double checked locking pattern:\n",
    "\n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "    static Singleton* object;\n",
    "    static std::mutex mtx;\n",
    "\n",
    "public:\n",
    "    static Singleton* instance()\n",
    "    {\n",
    "        if (!object)  // check 1\n",
    "        {\n",
    "            std::lock_guard guard(mtx);\n",
    "\n",
    "            if (!object)  // check 2\n",
    "                object = new Singleton;\n",
    "        }\n",
    "        return object;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "**Вопросы**: (чтобы тщательно разобрать код)\n",
    "* зачем нужна вторая проверка, будет ли код корректен без неё?\n",
    "* корректен ли код?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Со временем в этом шаблоне нашли хитрые race condition, что отчасти и подтолкнуло сообщество к формализации memory model в языках Java и С++.\n",
    "* до Java 2004 DCLP не работал [(подробности)](http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html)\n",
    "* до С++11 не было портируемого способа реализовать DCLP (стандарт не давал необходимых для этого инструментов и гарантий) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблема в этой строчке:\n",
    "    \n",
    "```c++\n",
    "object = new Singleton;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Программист мог бы подумать, что этот код выполняется в такой последовательности:\n",
    "* выделить память под `Singleton`\n",
    "* позвать конструктор `Singleton`\n",
    "* записать указатель в `object`\n",
    "\n",
    "Здесь в игру вступает instructions reordering.\n",
    "\n",
    "Например, если компилятор может доказать, что конструктор `Singleton` не бросает исключений, он вправе сгенерировать такой код:\n",
    "\n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "    static Singleton* object;\n",
    "    static std::mutex mtx;\n",
    "\n",
    "public:\n",
    "    static Singleton* instance()\n",
    "    {\n",
    "        if (!object)  // check 1\n",
    "        {\n",
    "            std::lock_guard guard(mtx);\n",
    "\n",
    "            if (!object)  // check 2\n",
    "            {\n",
    "                object = operator new(sizeof(Singleton));\n",
    "                new (object) Singleton;\n",
    "            }\n",
    "        }\n",
    "        return object;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "**Вопрос:** в чём здесь проблема? как её можно поймать?\n",
    "\n",
    "Как это пытались починить различными способами до стандартизации модели памяти, и почему они не работают - [в статье от Мейерса и Александреску](https://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Корректная реализация double checked locking pattern будет выглядеть так:\n",
    "\n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "    static std::atomic<Singleton*> object;\n",
    "    static std::mutex mtx;\n",
    "\n",
    "public:\n",
    "    static Singleton* instance()\n",
    "    {\n",
    "        auto* tmp = object.load();\n",
    "\n",
    "        if (!tmp)  // check 1\n",
    "        {\n",
    "            std::lock_guard<std::mutex> lock(mtx);\n",
    "\n",
    "            tmp = object.load();\n",
    "            if (!tmp)  // check 2\n",
    "            {\n",
    "                tmp = new Singleton;\n",
    "                object.store(tmp);\n",
    "            }\n",
    "        }\n",
    "        return tmp;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "В этом примере методы `load`/`store` у атомарных типов гарантируют корректный порядок операций между потоками.\n",
    "\n",
    "Как именно получаются гарантии и как сделать реализацию быстрее - рассмотрим позже, когда поговорим про memory model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если мы хотим ленивую инициализацию синглтона, то 11-ый стандарт даёт два варианта, которые скрывают проблемы DCLP от программиста:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант 1**: специальная конструкция для ленивых многопоточных синглтонов - `static`-переменные внутри функции:\n",
    "\n",
    "```c++\n",
    "class Singleton\n",
    "{\n",
    "public:\n",
    "    static Singleton& instance()\n",
    "    {\n",
    "        static Singleton object;\n",
    "        return object;\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "`static`-переменные внутри функций/методов (не путать с глобальными `static`-переменными!):\n",
    "* инициализируются лениво при первом обращении\n",
    "* компилятор с поддержкой С++11 обязан сгенерировать потокобезопасную инициализацию переменной. Компилятор не знает, будет этот код использован в многопоточном варианте или в однопоточном, поэтому он всегда генерирует безопасный многопоточный вариант\n",
    "* компилятор не обязан использовать DCLP, он может выбрать любой способ, который на его взгляд, работает лучше для данного случая, поэтому:\n",
    "\n",
    "```c++\n",
    "#include <string>\n",
    "\n",
    "float get_circle_area(const float radius)\n",
    "{\n",
    "    // скорее всего, здесь не будет никаких синхронизаций,\n",
    "    // но и static в этом месте - лишнее, лучше удалить\n",
    "    static const float pi = 3.14f;\n",
    "    return pi * radius * radius;\n",
    "}\n",
    "\n",
    "std::string add_12345(const std::string& x)\n",
    "{\n",
    "    // скорее всего, здесь будет синхронизация\n",
    "    static const std::string s = \"12345\";\n",
    "    return x + s;\n",
    "}\n",
    "```\n",
    "\n",
    "Закинуть на godbolt.org этот пример, показать."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос на понимание**: в чём разница этих трёх решений?\n",
    "\n",
    "```c++\n",
    "std::string add_12345_1(const std::string& x)\n",
    "{\n",
    "    static const std::string s = \"12345\";\n",
    "    return x + s;\n",
    "}\n",
    "```\n",
    "\n",
    "и\n",
    "\n",
    "```c++\n",
    "static const std::string s = \"12345\";\n",
    "\n",
    "std::string add_12345_2(const std::string& x)\n",
    "{\n",
    "    return x + s;\n",
    "}\n",
    "```\n",
    "\n",
    "и\n",
    "\n",
    "```c++\n",
    "std::string add_12345_3(const std::string& x)\n",
    "{\n",
    "    const std::string s = \"12345\";\n",
    "    return x + s;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант 2**: `std::call_once` (since C++11)\n",
    "\n",
    "https://en.cppreference.com/w/cpp/thread/call_once\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template< class Callable, class... Args >\n",
    "void call_once( std::once_flag& flag, Callable&& f, Args&&... args );\n",
    "```\n",
    "\n",
    "> Executes the Callable object `f` exactly once, even if called concurrently, from several threads.\n",
    "\n",
    "`std::call_once` позволяет гарантировать, что какая-то работа будет выполнена только один раз в многопоточной среде."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Более подробно про использование:\n",
    "\n",
    "```c++\n",
    "// какая-то работа, единоразовое выполнение которой нужно гарантировать\n",
    "void some_job(int param, int param2) {  /*...*/ }\n",
    "\n",
    "// где-то завели флажок, была ли выполнена работа\n",
    "// (специальный тип std::once_flag)\n",
    "std::once_flag my_flag;\n",
    "\n",
    "// вызываем std::call_once в любом потоке:\n",
    "std::vector<std::thread> threads;\n",
    "for (int i = 0; i != 5; ++i)\n",
    "    threads.emplace_back([&once_flag, i](){\n",
    "        /* .. */\n",
    "        \n",
    "        std::call_once(once_flag, some_job, i, i + 1);\n",
    "        \n",
    "        /* ... */        \n",
    "    });\n",
    "\n",
    "for (auto& t : threads)\n",
    "    t.join();\n",
    "```\n",
    "\n",
    "В этом примере гарантировано, что `some_job` *отработает* только единожды (с каким `param` - неизвестно, с которым первым получится). Когда `some_job` *отработает*, флаг `my_flag` будет взведён, и больше `some_job` не будет вызываться."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос**: какие в С++ есть (адекватные) стратегии обработки ошибок?\n",
    "\n",
    "<details>\n",
    "<summary>ответ</summary>\n",
    "\n",
    "код возврата и исключения\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`std::call_once` немножко хитрее, он умеет понимать, произошла ли ошибка в `some_job`. Если в `some_job` произошла ошибка, то он не считает, что работа выполнена.\n",
    "\n",
    "Ошибку `std::call_once` определяет по тому, вылетело ли из `some_job` исключение или выполнение функции завершилось стандартным способом.\n",
    "* Если выполнение завершается стандартным способом - флаг взводится, считается, что работа выполнена\n",
    "* Если вылетает исключение:\n",
    "  * флаг НЕ взводится\n",
    "  * исключение пролетает сквозь `std::call_once` наружу тому, кто `std::call_once` позвал \n",
    "  * следующий вызов `std::call_once` снова попытается выполнить работу"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**TODO**: добавить верхнеуровневое описание что присходит в примере или удалить (лучше?) его"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Разберём пример:\n",
    "\n",
    "```c++\n",
    "#include <atomic>\n",
    "#include <exception>\n",
    "#include <iostream>\n",
    "#include <mutex>\n",
    "#include <sstream>\n",
    "#include <string>\n",
    "#include <thread>\n",
    "#include <vector>\n",
    "\n",
    "std::atomic_int attempts_count{0};\n",
    "\n",
    "std::string s;\n",
    "\n",
    "void print_thread_msg(const std::string& message)\n",
    "{\n",
    "    std::stringstream ss;\n",
    "    ss << \"thread \" << std::this_thread::get_id() << ' ' << message << '\\n';\n",
    "    std::cout << ss.str();\n",
    "}\n",
    "\n",
    "void construct_object()\n",
    "{\n",
    "    const int before_add = attempts_count.fetch_add(1);\n",
    "    if (before_add < 5)\n",
    "    {\n",
    "        print_thread_msg(\"gets an attempt ix = \" + std::to_string(before_add) + \" and throws an exception\");\n",
    "        throw std::runtime_error(\"try again\");\n",
    "    }\n",
    "\n",
    "    print_thread_msg(\"gets an attempt ix = \" + std::to_string(before_add) + \" and constructs the value\");\n",
    "\n",
    "    s = \"hello c++\";\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    std::once_flag once_init_flag;\n",
    "\n",
    "    std::vector<std::thread> threads;\n",
    "    for (int i = 0; i != 10; ++i)\n",
    "        threads.emplace_back([&](){\n",
    "            try\n",
    "            {\n",
    "                std::call_once(once_init_flag, construct_object);\n",
    "            }\n",
    "            catch (const std::exception&) {}\n",
    "        });\n",
    "\n",
    "    for (auto& thr: threads)\n",
    "        thr.join();\n",
    "\n",
    "    std::cout << \"value is: \" << s << std::endl;\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопросы**:\n",
    "* сколько потоков создаётся?\n",
    "* сколько войдёт в `construct_object`?\n",
    "* какой ожидается вывод?\n",
    "* зачем отдельно вынесен такой страшный `print_thread_msg`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Скомпилируем пример clang-ом с clang-овской стандартной библиотекой libc++ и запустим:\n",
    "    \n",
    "```sh\n",
    "clang++-8 -O2 call_once.cpp -lpthread -stdlib=libc++\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод:\n",
    "\n",
    "```sh\n",
    "thread 139683658577664 gets an attempt ix = 0 and throws an exception\n",
    "thread 139683641792256 gets an attempt ix = 1 and throws an exception\n",
    "thread 139683650184960 gets an attempt ix = 2 and throws an exception\n",
    "thread 139683535251200 gets an attempt ix = 3 and throws an exception\n",
    "thread 139683510073088 gets an attempt ix = 4 and throws an exception\n",
    "thread 139683526858496 gets an attempt ix = 5 and constructs the value\n",
    "value is: hello c++\n",
    "```\n",
    "\n",
    "Обратите внимание, что после того как функция `construct_object`, переданная в `std::call_once`, завершила свою работу без пробрасывания исключений, больше никто `construct_object` не вызывает - работает гарантия `std::call_once`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь скомпилируем тот же самый код gcc со стандартной билиотекой libstdc++ и запустим:\n",
    "\n",
    "```sh\n",
    "g++ -O2 call_once.cpp -lpthread\n",
    "```\n",
    "\n",
    "И он... зависнет:\n",
    "\n",
    "```sh\n",
    "thread 139670308796160 gets an attempt ix = 0 and throws an exception\n",
    "# зависание тут\n",
    "```\n",
    "\n",
    "**Вопрос**: попробуйте догадаться, где ошибка?\n",
    "\n",
    "<details>\n",
    "<summary>ответ</summary>\n",
    "    \n",
    "В нашем коде ошибки нет, это [баг библиотеки libstdc++](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66146), известный ещё с 2015 года. В комбинации libstdc++ + posix threads не поддержана работа с исключениями в `std::call_once`. Можно для интереса зайти [на документацию `std::call_once`](https://en.cppreference.com/w/cpp/thread/call_once) и попробовать прогнать пример из документации.\n",
    "\n",
    "Мораль - даже если вы написали идеальный код по стандарту, не забудьте его протестировать перед тем как <s>показать студентам</s> выпустить в production.\n",
    "\n",
    "Тесты - хоть какая-то уверенность.\n",
    "    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Резюме** по блоку double checked locking pattern:\n",
    "* instructions reordering может принести неожиданные сюрпризы в многопоточных программах\n",
    "* гарантии на последовательность операций дают `std::atomic`-операции со стандарта С++11\n",
    "* если нужно лениво инициализировать глобальную переменную / константу, предпочтительнее использовать `static`-переменную внутри функции / метода, хороший компилятор выберет наиболее предпочтительный способ синхронизации для вашего случая.\n",
    "* если нужно гарантировать разовое выполнение работы в многопоточной среде - используйте связку `std::call_once + std::once_flag`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сравнение производительности `static` / `call_once` и других подходов:\n",
    "    \n",
    "http://www.modernescpp.com/index.php/thread-safe-initialization-of-a-singleton\n",
    "    \n",
    "Спойлер: `static` всех победил"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### spinlock && гибриды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос**: как устроен внутри `std::mutex`, что происходит при вызовах методов `lock`/`unlock`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В некоторых случаях использование `std::mutex` может оказаться слишком дорогим.\n",
    "\n",
    "Рассмотрим случай, когда защищаемый участок кода выполняется очень быстро:\n",
    "\n",
    "```c++\n",
    "std::vector<int> v;\n",
    "std::mutex mtx;\n",
    "\n",
    "void add_item(int item)\n",
    "{\n",
    "    std::lock_guard guard(mtx);\n",
    "    v.push_back(item);\n",
    "}\n",
    "```\n",
    "\n",
    "Зачастую `v.push_back` отрабатывает очень быстро, всего несколько инструкций: увеличить размер на 1 элемент и записать целое в область памяти. Время его работы значительно меньше, чем двойной уход в kernel space для `std::mutex` при вызовах `lock`/`unlock`. В такой функции всё время работы уходит на синхронизацию.\n",
    "\n",
    "Хочется подешевле.\n",
    "\n",
    "**Вопрос**: какой вариант после знакомства с сегодняшней лекцией вы могли бы предложить для таких блокировок?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`spinlock` - вариант решения проблемы на атомарных операциях.\n",
    "\n",
    "Простейшая его реализация:\n",
    "* атомарный флаг занятости\n",
    "* в `lock` подождать, пока флаг не станет \"свободным\", выставить \"занято\"\n",
    "* в `unlock` выставить \"свободно\"\n",
    "\n",
    "Вариант реализации (если понимать memory model, можно реализовать быстрее):\n",
    "\n",
    "https://en.cppreference.com/w/cpp/atomic/atomic_flag\n",
    "\n",
    "```c++\n",
    "class spin_lock\n",
    "{\n",
    "    std::atomic_flag busy = ATOMIC_FLAG_INIT;\n",
    "    \n",
    "public:\n",
    "    void lock()\n",
    "    {\n",
    "        // test_and_set - устанавливает флаг в true и\n",
    "        // возвращает предыдущее значение\n",
    "        //\n",
    "        // (если вернуло false, значит, это мы изменили\n",
    "        //  флаг false -> true)\n",
    "        \n",
    "        while (busy.test_and_set())  // acquire lock\n",
    "             ; // spin\n",
    "    }\n",
    "    \n",
    "    void unlock()\n",
    "    {\n",
    "        busy.clear();  // release lock\n",
    "    }\n",
    "};\n",
    "\n",
    "// Вопрос: почему это работает? как два потока будут бороться за lock?\n",
    "```\n",
    "\n",
    "И потом можно сделать так:\n",
    "\n",
    "```c++\n",
    "std::vector<int> v;\n",
    "spin_lock slock;\n",
    "\n",
    "void add_item(int item)\n",
    "{\n",
    "    std::lock_guard guard(slock);\n",
    "    v.push_back(item);\n",
    "}\n",
    "```\n",
    "\n",
    "и `add_item` начнёт работать значительно быстрее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос**: Если бы spinlock был так хорош, то можно было бы просто все `std::mutex` позаменять на spinlock и не мучиться. В чём проблема spinlock, чем он хуже `mutex`?\n",
    "\n",
    "<details>\n",
    "<summary>ответ</summary>\n",
    "<p>\n",
    "\n",
    "* `std::mutex` усыпляет висящий на его `lock`-е поток средствами ОС. Пока поток висит на `std::mutex`, ОС закинет на физическое ядро другие потоки, выполняющие полезную работу\n",
    "* `spinlock` оккупирует ядро в `lock` в цикле `while`, никому не отдавая свой фрейм выполнения. Если `spinlock` висит долго, он впустую крутит физическое ядро вместо того чтобы отдать ресурсы на полезную работу.\n",
    "\n",
    "</p>    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Поэтому для простых решений выработано правило:**\n",
    "* если блокируемый участок кода выполняется быстро - `spinlock`\n",
    "* если блокируемый участок кода выполняется медленно - `std::mutex`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть варианты частичного исправления проблемы `spinlock`-а - `spinlock` с засыпанием. Идея реализации метода `lock`:\n",
    "* покрутиться недолго на атомике в ожидании значения \"свободно\"\n",
    "* усыпить поток на время `x` (через `std::this_thread::yield`, например)\n",
    "* покрутиться недолго на атомике в ожидании значения \"свободно\"\n",
    "* усыпить поток на время `2 * x`\n",
    "* покрутиться недолго на атомике в ожидании значения \"свободно\"\n",
    "* усыпить поток на время `4 * x`\n",
    "* покрутиться недолго на атомике в ожидании значения \"свободно\"\n",
    "* усыпить поток на время `8 * x`\n",
    "...\n",
    "\n",
    "т.е. после некоторой оккупации физического ядра и кручения его на спинлоке всё-таки принять решение отдать ядро кому-то другому, а самому уснуть. Время засыпания увеличивать в геометрической прогрессии до некоторой верхней границы.\n",
    "\n",
    "Тоже допустимое решение, но `std::mutex` и здесь может начать выигрывать на длительных ожиданиях:\n",
    "* во время `std::this_thread::yield` поток не знает, когда проснуться, он будет спать запрошенное время, а событие разблокировки, например, произойдёт в середине сна.\n",
    "* к тому же остаются расходы на оккупацию физического ядра, но они меньше\n",
    "* в случае с `std::mutex` ОС знает, когда нужно разбудить ожидающий поток"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В случае, когда объём вычислений под блокировкой предсказать сложно (или не хочется думать), иногда используют гибридный вариант блокировки:\n",
    "* сначала покрутиться несколько раз на `atomic_flag`\n",
    "* если через atomic разрулить не получилось, уйти через `std::mutex` в kernel space, и пусть ОС сама решает когда нас разбудить\n",
    "\n",
    "Так, например, сделан [Webkit WTF::Lock](https://webkit.org/blog/6161/locking-in-webkit/) (статья объёмная, но полезная, почитайте)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания после лекции:**\n",
    "* выкинуть материал про task-based && thread-based - модели.\n",
    "* выкинуть материал про executors, слишком рано\n",
    "* упростить вводный пример с atomic. Начинать с такого большого кол-ва кода - некомильфо. Сравнение по производительности с mutex можно оставить на потом\n",
    "* пример про call_once и исключения - либо упростить, чтобы было меньше кода, либо выкинуть. Факт полезный, но съедает слишком много времени на объяснение.\n",
    "* пример с runtime instructions reordering упростить до 4-х переменных вместо 6\n",
    "* таки посмотреть во внутренности std::mutex, что там сейчас"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
